202502240002

Tags : Finite Model Theory

Even is $(MSO+<{)}_{\text{inv}}$-expressible

---

This is fairly easy. With Monadic Second Order Logic, one can quantify a set. If there exists a set which contains exactly half of the model then we are done, and $<$ lets us express that in the following formula:

$$\exists X(\exists xy,(\text{first}(x)\wedge \text{last}(y)\wedge \forall z(z\ne y\to z\in X⟺\text{next}(z)\notin X)\left)\right)$$

Where we have the following definitions:

• $\text{first}(x)\equiv \forall y,x\le y$
• $\text{last}(y)\equiv \forall x,x\le y$
• $\text{next}(w,z)\equiv \neg \exists x,w\le x\le z$

There has been a slight abuse of notation and $\text{next}$ has been defined as a function.

This also shows that $\text{MSO}⊊(\text{MSO}+<{)}_{\text{inv}}$

---

References